//239.滑动窗口最大值
//https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ret;
        ret.reserve(nums.size()-k+1);
        priority_queue<pair<int,int>> pq;
        for (int i = 0; i < k; ++i) pq.push({nums[i],i});
        ret.push_back(pq.top().first);
        for(int i = k;i<n;++i)
        {
            pq.push({nums[i],i});
            //i-k表示当前序列的最低端点值 如果堆顶值不在最低端点 则不在滑动窗口中
            //也可以写成 while(pq.top().second < i-k+1) pq.pop();
            //因为从0开始 下标+1 表示当前有效区间的最左区间 如果不在该区间 则堆顶为无效值
            while(pq.top().second <= i-k) pq.pop();
            ret.push_back(pq.top().first);
        }

        return ret;
    }
};